1. Field
Apparatuses and methods consistent with exemplary embodiments relate to reducing execution time of scheduling with a module, and more specifically, efficiently searching for a recurrence within a data dependency graph by software-pipelined scheduling with a module.
2. Description of the Related Art
A digital signal processor includes instructions programmed in a loop that repeatedly operates on the same data set. In order to enhance a processing speed of the loop, loop level parallelism (LLP) is frequently used. A representative example of LLP is software pipelining.
Software pipelining may simultaneously process a loop including multiple operations if there is no dependency between iterations in the loop which repeats the multiple operations. Thus, different repetitions may be processed in parallel by performing a subsequent iteration i+1 before a current iteration i is finished.
The software pipelining is used to optimize the loop by minimizing an initiation interval II which denotes a time interval between a start point of the iteration i and a start point of the subsequent iteration i+1.
A representative example of software pipelining is modulo scheduling. However, a lot of time is spent in searching for a recurrence in the data dependency graph in the modulo scheduling method, and thus, the total modulo scheduling performance time deteriorates.